package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class _104_maxDepth {
    //BFS
    public int maxDepth(TreeNode root) {
        if(root==null){return 0;}
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int levels = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size;i++){
                TreeNode node = queue.poll();
                if(node.left!=null){queue.add(node.left);}
                if(node.right!=null){queue.add(node.right);}
            }
            levels++;
        }
        return levels;
    }

    //DFS
    //递归，求左右子树的高度
    public int maxDepth1(TreeNode root) {
        if(root==null){return 0;}
        int left = maxDepth1(root.left);
        int right = maxDepth1(root.right);

        return Math.max(left,right)+1;
    }
}
